class Solution
{
    typedef pair<string, int> PSI;

    struct com
    {
        bool operator()(const PSI& a, const PSI& b)
        {
            if (a.second == b.second)
            {
                return a.first < b.first;
            }
            return a.second > b.second;
        }


    };


public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        unordered_map<string, int> hash;
        for (auto& s : words) hash[s]++;

        priority_queue<PSI, vector<PSI>, com> heap;
        for (auto& psi : hash)
        {
            heap.push(psi);
            if (heap.size() > k) heap.pop();
        }

        vector<string> ret(k);
        for (int i = k - 1; i >= 0; --i)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }

        return ret;
    }
};